package algorthm.systemTraning.dynamicPlanning;


/**
 * @className: RobotWalk
 * @Description:
 * @Author: wangyifei
 * @Date: 2024/3/20 21:02
 */
public class RobotWalk {
    /**
     * 在一个N*N的二维网格中，机器人从左上角出发，每次只能向下或者向右移动一步，问有多少种走法可以到达右下角？
     * 在一个 N 的一维线中，机器人从 start 的位置出发，在 K 步的情况下，走到 aim ，一个多少种走法
     * 并且当在 1 位置下一步，只能走到 2 位置，当走打开 N 位置，只能走到 N-1 位置 , 在其他位置，左右都能走
     */
    public static int walk(int N , int start , int aim , int K){
        return process1(start , K , aim , N);
    }
    public static int process1(int start , int rest , int aim , int N){
        if(rest == 0){
           return (start == aim ? 1 : 0);
        }
        if(1 == start){
            return process1(  2 , rest - 1 , aim ,N);
        }
        if(N == start){
            return process1(N - 1 , rest - 1 , aim ,N);
        }
        return process1(start + 1 , rest - 1 , aim ,N) + process1(start - 1 , rest - 1 , aim ,N);
    }

    /**
     * K 是总长度
     * N 是剩余的部署
     * @param K
     * @param
     * @param aim
     * @param N
     * @return
     */
    public static int process2(int K , int start , int aim , int N){
        // dp 二维数据，dp[j][i] 代表的业务意义是从 j 开始走 i 步，走完后到 aim 的方法数
        int[][] dp = new int[K+1][N+1];
        // dp[aim][0] 代表从 aim 开始走 0 步走到 aim 的方法只有 1 中，就是不动。
        dp[aim][0] = 1 ;
        for(int i = 1 ; i <= N ; i++){
            // 当 j = 1 时，只能往 2 走，所以 dp[1][i] = dp[2][i-1]
            dp[1][i] = dp[2][i-1];
            // 当 j 在中间的时候，可有左右走，所以 dp[j][i] 等于 ddp[j+1][i-1] + dp[j-1][i-1]
            for(int j = 2 ; j < K ; j++){
                dp[j][i] = dp[j+1][i-1] + dp[j-1][i-1];
            }
            // 当 j = K 时，只能往 K-1 走，所以 dp[K][i] = dp[K-1][i-1]
            dp[K][i] = dp[K-1][i-1];
        }
        return dp[start][N];
    }
    public static void main(String[] args) {
        System.out.println(walk(6, 3, 3, 6));
        System.out.println(process2(6, 3,   3, 8));
    }
}
